package baseclass.d_list;


import utils.ListNode;

import java.util.*;

/**
 * 链表排序
 *
 * @date 2020/2/28 22:27
 */
public class Code10_SortList {
    /**
     * 方式1：构建小根堆。遍历放入小根堆，然后重新构建。
     * 时间O(nlogn),空间O(n)
     */
    private static ListNode doSort(ListNode head) {
        ListNode cur = head;
        Queue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        while (cur != null) {
            queue.add(cur);
            cur = cur.next;
        }
        cur = new ListNode(-1);
        head = cur;
        while (!queue.isEmpty()) {
            //debug
            ListNode temp = queue.poll();
            System.out.println(temp.val);
            cur.next = temp;
            cur = cur.next;
        }
        //注意这里一定要让cur.next = null。不然会形成闭环。
        cur.next = null;
        return head.next;
    }

    /**
     * 方式2：开辟数组，把链表放入数组，对数组排序，然后重建。
     */
    private static ListNode doSort1(ListNode head) {
        List<ListNode> list = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        Collections.sort(list, (l1, l2) -> l1.val - l2.val);
        cur = new ListNode(-1);
        head = cur;
        int index = 0;
        while (index < list.size()) {
            cur.next = list.get(index++);
            cur = cur.next;
        }
        cur.next = null;
        return head.next;
    }

    /**
     * 方式3：递归版，额外辅助栈空间O(logn).
     * 把list分隔，最后再merge
     */
    private static ListNode process(ListNode head) {
        // step1  分
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        //slow最后在中间位置：奇数是中间 ，偶数是前一个
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        //隔断。前一半是head到slow，后一半是temp到tail
        slow.next = null;
        ListNode left = process(head);
        ListNode right = process(temp);
        //step2 合
        return mergeSortedList(left, right);
    }

    private static ListNode mergeSortedList(ListNode left, ListNode right) {
        ListNode cur;
        ListNode res;
        //合并left和right两个有序链表
        cur = new ListNode(-1);
        res = cur;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        //只有一个非空
        cur.next = left == null ? right : left;
        return res.next;
    }


}
